/*
    Author: Christopher Diggins
    License: MIT Licence 1.0
    Website: http://www.cdiggins.com
*/

#ifndef CVML_PARAMETERIZED_SUBGEN_HPP
#define CVML_PARAMETERIZED_SUBGEN_HPP

// Note: will not extend past "return" instructions.
bool ExtendIfSame(InstrSeq& seq1, InstrSeq& seq2) {
	if (seq1.end == NULL || seq2.end == NULL)
		return false;
	if (!seq1.end->Matches(*seq2.end))
		return false;	
	seq1.end = seq1.end->next;
	seq2.end = seq2.end->next;
	if (seq1.end == NULL || seq2.end == NULL)
		return false;	
	if (seq1.end->next == NULL || seq2.end->next == NULL)
		return false;
	return seq1.end->Matches(*seq2.end);
}

bool IsValidSuffix(Instruction* a, Instruction* b) {
	if (a == b || a == NULL || b == NULL)
		return false;
	if (a->GetHashCode() != b->GetHashCode())
		return false;
	if (a->next == NULL || b->next == NULL)
		return false;	
	if (a->next == b || b->next == a)
		return false;
	if (a->next->GetHashCode() != b->next->GetHashCode())
		return false;
	if (a->next->opcode == op_ret)
		return false;
	return true;
}

bool AttemptSubMerge(ByteCode* bc, InstrSeq seq1, InstrSeq seq2) {
	InstrSeq prefix1 = seq1;
	InstrSeq prefix2 = seq2;

	while (ExtendIfSame(prefix1, prefix2)) { }
	Assert(prefix1.Len() == prefix2.Len());
	
	if (prefix1.Overlaps(prefix2)) 
		return false;
	if (prefix1.end == NULL || prefix2.end == NULL)
		return false;

	bool bValidSuffix = false;
	Instruction* suffixBegin1 = NULL;
	Instruction* suffixBegin2 = NULL;
	for (Instruction* a = prefix1.end; a != NULL && !bValidSuffix; a = a->next) {
		for (Instruction* b = prefix2.end; b != NULL && !bValidSuffix; b = b->next) {
			if (IsValidSuffix(a, b)) {
				bValidSuffix = true;
				suffixBegin1 = a;
				suffixBegin2 = b;
			}
		}
	}
	if (!bValidSuffix) 
		return false;

	InstrSeq mid1(prefix1.end, suffixBegin1);
	InstrSeq mid2(prefix2.end, suffixBegin2);

	if (mid1.Overlaps(mid2))
		return false;

	InstrSeq suffix1(suffixBegin1, suffixBegin1->next);
	InstrSeq suffix2(suffixBegin2, suffixBegin2->next);
	
	while (ExtendIfSame(suffix1, suffix2)) { }
	if (suffix1.Overlaps(suffix2))
		return false;
	Assert(suffix1.Len() == suffix2.Len());

	if (suffix1.Len() < 2)
		return false;

	// If the prefix plus suffix constitute only four instructions
	// the heuristic is that it will probably not prove beneficial
	if (suffix1.Len() + prefix1.Len() < 5) 
		return false;

    // Create the new subroutines
    Subroutine* subPrefix = CreateSubFromSeq(bc, prefix1);
	Subroutine* subSuffix = CreateSubFromSeq(bc, suffix1);
	Instruction* tmp = subSuffix->first;
	subSuffix->first = new Instruction(op_sap);
	subSuffix->first->next = tmp;
	Subroutine* subMid1 = CreateSubFromSeq(bc, mid1);
	Subroutine* subMid2 = CreateSubFromSeq(bc, mid2);
	
	// Rewrite code
	tmp = seq1.begin;
	tmp->SetOpCode(op_push_sub, subMid1); 
	tmp = tmp->next;
	tmp->SetOpCode(op_push_sub, subSuffix); 
	tmp = tmp->next;
	tmp->SetOpCode(op_apply); 
	tmp = tmp->next;
	while (tmp != suffix1.end) {
		tmp->SetNoop();
		tmp = tmp->next;
	}

	tmp = seq2.begin;
	tmp->SetOpCode(op_push_sub, subMid2); 
	tmp = tmp->next;
	tmp->SetOpCode(op_push_sub, subSuffix); 
	tmp = tmp->next;
	tmp->SetOpCode(op_apply); 
	tmp = tmp->next;
	while (tmp != suffix2.end) {
		tmp->SetNoop();
		tmp = tmp->next;
	}

	return true;
}

bool GenerateParameterizedSub(ByteCode* bc, Subroutine* sub) {
	PrefixTree* prefixes = CreatePrefixTree(bc, 2);
    std::vector<PrefixTree::Node*> leaves;
    prefixes->GetLeaves(leaves);
	for (size_t i=0; i < leaves.size(); ++i) {
		PrefixTree::Node* node = leaves[i];
		for (size_t j=0; j < node->seqs.size() - 1; ++j) 
		for (size_t k=j + 1; k < node->seqs.size(); ++k) 
		{
			if (AttemptSubMerge(bc, node->seqs[j], node->seqs[k]))
				return true;
		}
	}
	return false;
}

void GenerateParameterizedSubs(ByteCode* bc) {
	bool bFixPoint = false;
	while (!bFixPoint) {
		bFixPoint = true;
		for (int i=0; i < bc->GetNumSubs(); ++i) {
			if (GenerateParameterizedSub(bc, bc->GetSub(i))) {
				bFixPoint = false; 
				break;
			}
		}
	}
}

#endif
